package com.learn.string;

/**
 * KMP算法用于求解字符串的字串问题
 */
public class KMP {


    public int getIndex(String original, String match) {
        if (original.length() == 0 || match.length() == 0 || original.length() < match.length()) {
            return -1;
        }

        char[] originalArr = original.toCharArray();
        char[] matchArr = match.toCharArray();
        int[] next = getNextArr(match);
        int x = 0;
        int y = 0;

        while (x < originalArr.length && y < matchArr.length) {
            if (originalArr[x] == matchArr[y]) {
                x++;
                y++;
            } else if (next[y] != -1) {
                y = next[y];
            } else {
                x++;
            }


        }


        return y == matchArr.length ? x - y : -1;

    }

    /**
     * 创建辅助数组，arr[i]位置代表0~i-1位置的前缀字符串和后缀字符串的长度
     *
     * @param str
     * @return
     */
    public int[] getNextArr(String str) {
        if (str.length() == 1) {
            return new int[]{-1};
        }

        char[] match = str.toCharArray();
        int[] res = new int[match.length];
        res[0] = -1;
        res[1] = 0;
        int i = 2;
        //代表两层含义，i-1时的前缀长度，需要跳到cn位置进行字符串比较
        int cn = 0;

        while (i < match.length) {
            if (match[i - 1] == match[cn]) {
                //当i-1位置的字符与cn长度的前缀的后一位字符相等时，i位置的前缀长度就为cn+1,
                res[i++] = ++cn;
            } else if (cn > 0) {
                //之前位置不等，cn需要继续向前回跳
                cn = res[cn];
            } else {
                //当前i位置的前缀为0
                res[i++] = 0;
            }

        }
        return res;
    }
}
